Internet protocol networks are handling increasing volumes of data, with the data being of different types. For example, potential high value Internet services, such as voice and video, generate mostly constant bit-rate, inelastic traffic which is difficult to adapt to a change in network environment. Such traffic competes for bandwidth with data transfers, such as email and the like, which are much more reactive to changing network conditions. When congestion occurs, all traffic to a congested node is affected, meaning that packets can then be lost at the node. The consequences of packet loss for a particular data stream can vary, depending on the type of the stream. For voice-over-IP (VoIP), telephony, and video applications, packet losses manifest themselves as artefacts in the received audio or video, such as the audio breaking up, or videos having the image freeze.
It has therefore long been known that to try and protect high value Internet services, such as voice and video, a quality of service (QoS) mechanism is required, to try and guarantee the level of network service to such high value streams. For example, the Differentiated Services (DiffServ) architecture allows packet streams to be distinguished amongst different classes, and for a different quality of service to be offered to each packet class. High value services such as voice-over-IP, video, and the like will be placed in a higher class with a higher quality of service than lower value services. The Internet protocol header contains the DiffServ code point (DSCP), to allow an IP datagram to be categorised into the particular classes for use with a DiffServ architecture.
Another technique which has been applied is to control admission of data flows into a network, so as to only admit a sufficient number of data flows for which the network has capacity. This is known as admission control. In this field, recently measurement-based admission control (MBAC) has been of interest. One particular MBAC solution is known as pre-congestion notification (PCN) which has been developed by the Congestion and Pre-congestion Notification working group of the Internet Engineering Taskforce. A description of the present status of PCN can be found at http://tools.ietf.org/html/draft-ietf-pcn-architecture-03.
The basic idea of PCN is to control the admission of flows to a region of the network by means of a periodic measurement of the congestion level between two edges of that region. Congestion signals are propagated throughout the network towards egress nodes, as shown in FIG. 1. In particular, here it will be seen that as a flow 18 propagates from an ingress node 12 towards an egress node 14, congestion signals can be added to the flow 18 which are then measured at the egress node 14 and fed back to the ingress node 12. Explicit congestion notification (ECN), as described in IETF RFC 3168, is used to add congestion marks to the DiffServ code point of the IP packets on flow 18 so as to propagate a congestion notification signal downstream to the egress node. The egress node measures the receipt of congestion marks in the packets which it receives in the flow, and feeds back information as to the level of congestion on path 18 to the ingress node 12, as congestion information 19.
When a new flow arrives at ingress node 12 this node compares the current congestion level which has been experienced with a preconfigured threshold stored in table 16, and a new flow is admitted only when the actual congestion which has been experienced is lower than the preconfigured congestion threshold. With the values shown in table 16 of FIG. 1, a new flow would be admitted.
One of the problems with the prior art PCN mechanism is that it concentrates solely on admission control, and does not take into account the actual path that a flow takes through a network. For example, it may be that only a subset of paths through a network are in fact very heavily congested, with the remainder of the paths being only lightly congested. However, depending on the congestion thresholds chosen, and the congestion measurements used, the heavily congested paths may influence the overall congestion measurement to the extent that flows are rejected, even though there is in fact capacity on some of the paths. However, only by taking into account both path routing and admission control at the same time, can this problem be addressed.
One piece of prior art which performs admission control and routing simultaneously is U.S. Pat. No. 6,778,496 B, issued to Lucent. Within the Lucent patent, an admission control and load balancing technique is described which allows for congestion information to propagate from the ingress node of a network down to the egress node. The congestion information is in the form of a cost metric which is updated as the cost packet travels along the path. The cost metric packet is received at the egress gateways, and can be used for an admission control decision at the egress gateways by comparing the cost metric thus determined with a constant admission threshold, and admitting new flows into the network if the cost metric is less than the admission threshold. The admission control decision must then be communicated to the ingress nodes. FIG. 2 illustrates a simplified version of such a scheme. Here, cost metric packets (referred to in Lucent as “path utilisation status messages”) propagate through the network from an ingress node to egress nodes, collecting cost information along the way. Admission control decisions can then be taken at the egress nodes by comparing the measured cost with the threshold. Additionally, path selection through the network can also be performed at the same time by selecting the most appropriate path based on the cost metrics thus found.
Whilst Lucent therefore integrates the admission control and multipath routing decision, it continues to have some drawbacks due to the particular implementation used. For example because Lucent depends upon a constant admission control threshold, the problem noted previously can still be found, that the threshold may be set incorrectly so as to cause some flows to be refused, when in fact they could be admitted. It would therefore be preferable for a further, more intelligent, admission control and multipath routing technique to be found which does not have the drawbacks of the use of fixed thresholds for admission control decisions.
US 2002/120768 in the name of Kirby et al relates to traffic flow management in a communications network. Admission of rapidly varying traffic flows to a communications network is controlled by sampling the traffic flows at an ingress, and sampling an aggregate flow of the flows at some or all of the resources used by the aggregate flow. From this sampling, a mean bandwidth requirement for each traffic flow and a measure of the variance from that mean are determined. First and second prices for the mean and variance components of the controlled traffic flows are calculated, and these are used to determine an admission cost for each flow so as to regulate the admission of that flow via a feedback price mechanism.
EP 0 777 362, also in the name of Lucent, relates to a method of admitting and routing switched virtual circuit (VC) requests in a network. The method first finds a set of routing paths on which a requested VC may be routed using a two-step process. The method uses a cost function based on a parameter related to the number of hops in a subset of VC connections previously made in the network to determine potential routing paths on which the VC can be routed at a cost below a specified threshold. The method next checks to determine which potential routing paths comprise links and nodes with sufficient resources to accommodate the request. Paths satisfying both steps are output as a set of routing paths and then a second criterion is used to select a path from the set on which to route the request.